/*!
 Temelia - Scapegoat tree interface.

 Copyright (C) 2008, 2009 Ceata (http://cod.ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#ifndef SCAPEGOAT_TREE_H_
#define SCAPEGOAT_TREE_H_

#include "platform.h"
#include "binary_tree_common.h"

struct _scapegoat_tree_t;
typedef struct _scapegoat_tree_t *scapegoat_tree_t;

/*!
 * @brief Returns an empty scapegoat tree.
 * Complexity O(1)
 *
 * @param Alpha - this parameter defines the relation between a node's height
 * and it's depth : height <= floor(log(depth)/log(1/alpha)). If you choose alpha
 * to be ~0.5 then the tree will be a slower variant of AVL trees
 */
DECLSPEC scapegoat_tree_t scapegoat_tree_new(double alpha);

/*!
 * @see binary_tree_delete_node
 */
DECLSPEC void scapegoat_tree_delete_node(scapegoat_node_t scapegoat);

/*!
 * @see binary_tree_delete
 */
DECLSPEC void scapegoat_tree_delete(scapegoat_tree_t scapegoat);

/*!
 * @see binary_tree_compare_trees
 */
DECLSPEC int
scapegoat_tree_compare_trees(scapegoat_tree_t scapegoat1,
		scapegoat_tree_t scapegoat2, int compare(void *x, void *y,
				void *context), void *context);

/*!
 * @see binary_tree_is_empty
 */
DECLSPEC int scapegoat_tree_is_empty(scapegoat_tree_t scapegoat);

/*!
 * @see binary_tree_is_leaf
 */
DECLSPEC int scapegoat_tree_is_leaf(scapegoat_node_t scapegoat);

/*!
 * @see binary_tree_get_size.
 */
DECLSPEC int scapegoat_tree_get_size(scapegoat_tree_t scapegoat);

/*!
 * @brief Returns the alpha parameters of this scapegoat tree.
 * Complexity O(1)
 *
 * @param Scapegoat tree
 */
DECLSPEC double scapegoat_tree_get_alpha(scapegoat_tree_t scapegoat);

/*!
 * @see binary_tree_get_root
 */
DECLSPEC scapegoat_node_t scapegoat_tree_get_root(scapegoat_tree_t scapegoat);

/*!
 * @see binary_tree_get_root
 */
DECLSPEC scapegoat_node_t scapegoat_tree_get_node_root(scapegoat_node_t scapegoat);

/*!
 * @see binary_tree_get_key
 */
DECLSPEC void *scapegoat_tree_get_key(scapegoat_node_t scapegoat);

/*!
 * @see binary_tree_get_parent
 */
DECLSPEC scapegoat_node_t scapegoat_tree_get_parent(scapegoat_node_t scapegoat);

/*!
 * @see binary_tree_get_left_child
 */
DECLSPEC scapegoat_node_t
scapegoat_tree_get_left_child(scapegoat_node_t scapegoat);

/*!
 * @see binary_tree_get_right_child
 */
DECLSPEC scapegoat_node_t scapegoat_tree_get_right_child(scapegoat_node_t scapegoat);

/*!
 * @see binary_tree_get_height
 */
DECLSPEC int scapegoat_tree_get_height(scapegoat_tree_t scapegoat);

/*!
 * @see binary_tree_get_height
 */
DECLSPEC int scapegoat_tree_get_node_height(scapegoat_node_t scapegoat);

/*!
 * @see binary_tree_get_depth
 */
DECLSPEC int scapegoat_tree_get_depth(scapegoat_node_t scapegoat);

/*!
 * @see binary_search_tree_search
 */
DECLSPEC scapegoat_node_t scapegoat_tree_search(scapegoat_tree_t scapegoat, void *key,
		int compare(void *x, void *y, void *context), void *context);

/*!
 * @see binary_search_tree_insert
 */
DECLSPEC scapegoat_node_t scapegoat_tree_insert(scapegoat_tree_t scapegoat, void *key,
		int compare(void *x, void *y, void *context), void *context);

/*!
 * @see binary_search_tree_remove; the root is adjusted
 */
DECLSPEC scapegoat_node_t scapegoat_tree_remove(scapegoat_tree_t scapegoat_tree_,
		void *key, int compare(void *x, void *y, void *context), void *context);

/*!
 * @see binary_search_tree_get_min
 */
DECLSPEC scapegoat_node_t scapegoat_tree_get_min(scapegoat_tree_t scapegoat);

/*!
 * @see binary_search_tree_get_max
 */
DECLSPEC scapegoat_node_t scapegoat_tree_get_max(scapegoat_tree_t scapegoat);

/*!
 * @see binary_tree_preorder
 */
DECLSPEC void scapegoat_tree_preorder(scapegoat_tree_t scapegoat, void key_handler(
		void *x, void *context), void *context);
/*!
 * @see binary_tree_inorder
 */
DECLSPEC void scapegoat_tree_inorder(scapegoat_tree_t scapegoat, void key_handler(
		void *x, void *context), void *context);

/*!
 * @see binary_tree_reverse_inorder
 */
DECLSPEC void scapegoat_tree_reverse_inorder(scapegoat_tree_t scapegoat,
		void key_handler(void *x, void *context), void *context);

/*!
 * @see binary_tree_postorder
 */
DECLSPEC void scapegoat_tree_postorder(scapegoat_tree_t scapegoat, void key_handler(
		void *x, void *context), void *context);

/*!
 * @see binary_tree_level_order
 */
DECLSPEC void scapegoat_tree_level_order(scapegoat_tree_t scapegoat, void key_handler(
		void *x, void *context), void *context);

/*!
 * @see binary_tree_show_indented
 */
DECLSPEC void scapegoat_tree_show_indented(scapegoat_tree_t scapegoat, void key_handler(
		void *x, int level, void *context), void *context);

#endif /* SCAPEGOAT_TREE_H_ */
